#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#define SKIPLIST_MAXLEVEL 32
#define SKIPLIST_P 0.25

typedef struct skiplistNode {
    void *obj;
    int score;
    /* 后退指针 */
    struct skiplistNode *backward;
    struct skiplistLevel {
        /* 前进指针 */
        struct skiplistNode *forward;
    } level[];
} skiplistNode;

typedef struct skiplist {
    struct skiplistNode *header, *tail;
    // 表中节点的数量
    unsigned long length;
    // 表中层数最大的节点的层数
    int level;
} skiplist;

skiplistNode *createNode(int level, double score, void *obj) {
    skiplistNode *node = malloc(sizeof(*node)+level*sizeof(struct skiplistLevel));
    node->score = score;
    node->obj = obj;
    return node;
}

skiplist *skipListCreate(void) {
    int i;
    skiplist *list;

    list = malloc(sizeof(*list));
    list->level = 1;
    list->length = 0;
    list->header = createNode(SKIPLIST_MAXLEVEL, -1, NULL);
    for (i = 0; i < SKIPLIST_MAXLEVEL; i++) {
        list->header->level[i].forward = NULL;
    }
    list->header->backward = NULL;
    list->tail = NULL;
    return list;
}

void freeNode(skiplistNode *node) {
    free(node);
}

void skipListFree(skiplist *list) {
    skiplistNode *node = list->header->level[0].forward, *next;

    free(list->header);
    while (node) {
        next = node->level[0].forward;
        freeNode(node);
        node = next;
    }
    free(list);
}

int randomLevel(void) {
    int level = 1;
    while ((random() & 0xFFFF) < (SKIPLIST_P * 0xFFFF))
        level += 1;
    return (level < SKIPLIST_MAXLEVEL) ? level : SKIPLIST_MAXLEVEL;
}

skiplistNode *insertNode(skiplist *list, int score, void *obj) {
    skiplistNode *update[SKIPLIST_MAXLEVEL], *x;
    int i, level;

    x = list->header;
    // 保存新增节点的所有前置节点及其
    for (i = list->level-1; i >= 0; i--) {
        while (x->level[i].forward && x->level[i].forward->score < score) {
            x = x->level[i].forward;
        }
        update[i] = x;
    }

    level = randomLevel();
    if (level > list->level) {
        for (i = list->level; i < level; i++) {
            update[i] = list->header;
        }
        list->level = level;
    }

    // 更新节点的前指针
    x = createNode(level, score, obj);
    for (i = 0; i < level; i++) {
        // 调整链表指向，修改各个层级的链表指向
        x->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = x;
    }

    // 更新节点的后指针
    x->backward = (update[0] == list->header) ? NULL : update[0];
    if (x->level[0].forward)
        x->level[0].forward->backward = x;
    else
        list->tail = x;
    list->length++;
    return x;
}

skiplistNode *findNodeByScore(skiplist *list, int score) {
    skiplistNode *node, *next;
    int i;

    node = list->header;
    for (i = list->level - 1; i >= 0; i--) {
		next = node->level[i].forward;
        while (next && next->score <= score) {
			if (next->score == score) {
				return next;
			}
            node = next;
			next = node->level[i].forward;
        }
    }
    return NULL;
}

void deleteNode(skiplist *list, skiplistNode *x, skiplistNode **update) {
    int i;
    for (i = 0; i < list->level; i++) {
        if (update[i]->level[i].forward == x) {
            update[i]->level[i].forward = x->level[i].forward;
        }
    }
    if (x->level[0].forward) {
        x->level[0].forward->backward = x->backward;
    } else {
        list->tail = x->backward;
    }
    while(list->level > 1 && list->header->level[list->level-1].forward == NULL)
        list->level--;
    list->length--;
}

int deleteNodeByScore(skiplist *list, double score) {
    skiplistNode *update[SKIPLIST_MAXLEVEL], *x;
    int i;

    x = list->header;
    for (i = list->level-1; i >= 0; i--) {
        while (x->level[i].forward && x->level[i].forward->score < score) {
            x = x->level[i].forward;
        }
        update[i] = x;
    }
    x = x->level[0].forward;
    if (x && x->score == score) {
        deleteNode(list, x, update);
        freeNode(x);
    }
    // not found
	return 0;
}

void printfNode(skiplistNode *node) {
    if (node) {
	    printf("score=%d, value=%s\n", node->score, (char *) node->obj);
    } else {
		printf("node not found\n");
    }
}

/**
 * |_-1_|<---|_07_|<---|_14_|<---|_21_|<---|_32_|<---|_37_|<---|_71_|<---NULL
 * |____|----------------------->|____|------------->|____|------------->NULL
 * |____|--->|____|------------->|____|------------->|____|--->|____|--->NULL
 * |____|--->|____|--->|____|--->|____|--->|____|--->|____|--->|____|--->tail
 */
void main() {
    skiplist *list = skipListCreate();
    insertNode(list, 21, "aaa");
    insertNode(list, 37, "bbb");
    insertNode(list, 7, "ccc");
    insertNode(list, 71, "ddd");
    insertNode(list, 14, "eee");
    insertNode(list, 32, "fff");

    skiplistNode *node;

    node = findNodeByScore(list, 17);
	printfNode(node);
    node = findNodeByScore(list, 71);
	printfNode(node);
	deleteNodeByScore(list, 71);
    node = findNodeByScore(list, 71);
	printfNode(node);
	
	insertNode(list, 24, "sss");
	insertNode(list, 9, "ttt");
	node = findNodeByScore(list, 9);
	printfNode(node);

    skipListFree(list);
}
